﻿// 0804train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;

/*
 区块链底层存储是一个链式文件系统，由顺序的 N 个文件组成，每个文件的大小不一，
 依次为F1, F2, …, Fn 。
 假设每块 SATA 盘容量为 M，求能转储的最大连续文件大小之和。
输入描述
第一行为 SATA 盘容量 M，1000 ≤ M ≤ 1000000
第二行为区块链文件大小序列 F1, F2, …, Fn。其中 1 ≤ n ≤ 100000，1 ≤ Fi ≤ 500
输出描述
求能转储的最大连续文件大小之和。

示例1
输入
1000
100 300 500 400 400 150 100
输出
950

示例2
输入
1000
100 500 400 150 500 100
输出
1000
 */

void solve01(int target, vector<int>&oh_vec)
{
    vector<int>queue_vec;
    int result = -1;
    int sum = 0;
    int vec_size = oh_vec.size();
    for (int i=0; i<vec_size; i++)
    {
        int curr_num = oh_vec[i];
        sum += curr_num;
        
        while ((!queue_vec.empty()) && (sum > target))
        {
            int front = queue_vec[0];
            queue_vec.erase(queue_vec.begin());
            sum -= front;
        }
        queue_vec.push_back(curr_num);
        if (sum<=target)
        {
            result = max(result, sum);
        }
        //for-----
    }

    cout << result;

    //solve01
}


/*
 给定一个字符串 s ，找出这样一个子串：
1. 该子串中的任意一个字符最多出现 2 次；
2. 该子串不包含指定某个字符；
请你找出满足该条件的最长子串的长度。
输入
第一行为要求不包含的指定字符，为单个字符，取值范围 [0-9a-zA-Z]
第二行为字符串 s，每个字符范围 [0-9a-zA-Z]，长度范围 [1,10000]

输出
一个整数，满足条件的最长子串的长度；
如果不存在满足条件的子串，则返回 0

示例1
输入
D
ABC123
输出
6

示例2
输入
D
ABACD1231
输出
4
 */

void solve02(string&t, string& s)
{
    //次数超过2，收缩左窗
    //右窗碰到D，左右同时移到D+1的位置
    unordered_map<char, int>oh_map;
    string oh_str = s;
    char target_char = t[0];
    int str_size = oh_str.size();

    int left_index = 0;
    int right_index = 0;

    int result = -1;
    
    while (right_index < str_size)
    {
        char curr_char = oh_str[right_index];
        if (curr_char == target_char)
        {
            //right_index-1-left_index+1 = right_index-left_index
            result = max(result, right_index-left_index);
            
            if (right_index+1<str_size)
            {
                right_index += 1;
                left_index = right_index;
                oh_map.clear();
                continue;
            }
            else
            {
                break;
            }
            
        }
        oh_map[curr_char] += 1;
        while (oh_map[curr_char]>2)
        {
            char left_char = oh_str[left_index];
            oh_map[left_char] -= 1;
            left_index += 1;
        }
        result = max(result, right_index - left_index+1);
        right_index += 1;
        //while------
    }
    cout << result;
    //solve02------
}


/*
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。
删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例1
输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例2
输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
 */

int solve03(vector<int>&nums)
{
    vector<int>oh_vec = nums;
    int vec_size = oh_vec.size();
    unordered_set<int>oh_set;

    int left_index = 0;
    int right_index = 0;
    int result = -1;
    int sum = 0;
    while (right_index < vec_size)
    {
        int curr_num = oh_vec[right_index];
        while (oh_set.count(curr_num))
        {
            int left_num = oh_vec[left_index];
            sum -= left_num;
            oh_set.erase(left_num);
            left_index += 1;
        }

        sum += curr_num;
        result = max(result, sum);
        oh_set.insert(curr_num);
        right_index += 1;
        //while
    }

    return result;
    //solve03------
}


/*
 一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。
 老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。
 （也就是连续出现 true 或者连续出现 false）。
给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。
除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：
- 每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。
请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

示例 1：
输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

示例 2：
输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。

示例 3：
输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。
 */
int solve04(string&answerKey, int k)
{
    //至多包含k个T或k个F的滑窗的最大长度
    string oh_str = answerKey;
    int str_size = oh_str.size();
    int left_index = 0;

    int result = 0;
    int limit = k;
    int t_count = 0, f_count = 0;

    for (int right_index=0; right_index<str_size; right_index++)
    {
        char curr_char = oh_str[right_index];

        if (curr_char=='T')
        {
            t_count++;
        }
        else
        {
            f_count++;
        }

        //至关重要的一步，不管是t_count，还是f_count都可以
        while (min(t_count,f_count)>limit)
        {
            char left_char = oh_str[left_index];
            if (left_char=='T')
            {
                t_count--;
            }
            else
            {
                f_count--;
            }
            left_index++;
        }
        result = max(result, right_index - left_index + 1);
        //for------
    }
    return result;
    //solve04------
}

int main()
{
	{
        //answerKey = "TFFT", k = 1 3
        //answerKey = "TTFTTFTT", k = 1 5
        string answerKey = "TFFT";
        int k = 1;
        cout << solve04(answerKey, k);

        return 0;
	}

	{
        //nums = [4,2,4,5,6] 17
        //nums = [5,2,1,2,5,2,1,2,5] 8
        vector<int>nums = { 5,2,1,2,5,2,1,2,5 };
        cout << solve03(nums);

        return 0;
	}

	{
        //D
        //ABACD1231
        //d
        //awe9goieIAOI90w9urwe09
        //0
        //fwmt0940myu59M0C9WUMw0mtu0
        //s
        //asfiadigohads
        string target_char = "s";
        string oh_str = "asfiadigohads";
        //string target_char;
        //cin >> target_char;
        //string oh_str;
        //cin >> oh_str;
        solve02(target_char, oh_str);

        return 0;
	}

    //1000
	//100 300 500 400 400 150 100
    //950
	//------
    //1000
    //100 500 400 150 500 100
    //1000
    //vector<int>oh_vec = { 100,500,400,150,500,100 };
    //int target = 1000;

    int target;
    cin >> target;
    cin.ignore();

    vector<int>oh_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (oh_sstream>>token)
    {
        oh_vec.push_back(stoi(token));
    }

    //for (auto&num:oh_vec)
    //{
    //    cout << num << ' ';
    //}

    solve01(target, oh_vec);

    //main-----
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
